#include <iostream>
#include <string.h>
#include <assert.h>
using namespace std;

class Mystring
{
public:
  Mystring(const char *str = "")
  {
    _size = strlen(str);
    _capacity = _size;
    _str = new char[_capacity + 1];
    strcpy(_str, str);
  }

  Mystring(const Mystring &str)
  {
    _size = str._size;
    _capacity = str._capacity;
    _str = new char[_capacity + 1];
    memcpy(_str, str._str, _size + 1);
  }

  // Mystring(const Mystring &str)
  //   :_str(nullptr),
  //   _size(0),
  //   _capacity(0)
  //{
  //   Mystring tmp(str._str);
  //   swap(tmp);
  // }

  ~Mystring()
  {
    delete[] _str;
  }

  void swap(Mystring &str)
  {
    ::swap(_str, str._str);
    ::swap(_size, str._size);
    ::swap(_capacity, str._capacity);
  }

  Mystring &operator=(const Mystring &str)
  {
    if (this != &str)
    {
      char *tmp = new char[str._capacity + 1];
      memcpy(tmp, str._str, str._size + 1);

      delete[] _str;
      _str = tmp;
      _size = str._size;
      _capacity = str._capacity;
    }
    return *this;
  }

  // Mystring& operator=(const Mystring &str)
  //{
  //   cout << "operator=" << endl;
  //   if(this != &str)
  //   {
  //     Mystring tmp(str._str);
  //     swap(tmp);
  //   }
  //   return *this;
  // }

  // Mystring& operator=(Mystring str){
  //   cout << "operator=" << endl;
  //   swap(str);
  //   return *this;
  // }

  void reserve(size_t newcapacity)
  {
    if (newcapacity > _capacity)
    {
      char *tmp = new char[newcapacity + 1];
      memcpy(tmp, _str, _size + 1);
      delete[] _str;
      _str = tmp;
      _capacity = newcapacity;
    }
  }

  void resize(size_t newsize, char ch = '\0')
  {
    if (newsize > _size)
    {
      reserve(newsize);
      for (size_t i = _size; i < newsize; ++i)
      {
        _str[i] = ch;
      }
    }
    _str[newsize] = '\0';
    _size = newsize;
  }

  void push_back(char ch)
  {
    if (_size == _capacity)
    {
      size_t newcapacity = _capacity == 0 ? 5 : 2 * _capacity;
      reserve(newcapacity);
    }
    _str[_size] = ch;
    ++_size;
    _str[_size] = '\0';
  }

  Mystring &operator+=(char ch)
  {
    push_back(ch);
    return *this;
  }

  void append(const char *str)
  {
    size_t len = strlen(str);
    reserve(len + _size);
    strcpy(_str + _size, str);
    _size += len;
  }

  void append(const Mystring &str)
  {
    size_t newsize = _size + str._size;
    reserve(newsize);
    memcpy(_str + _size, str._str, str._size + 1);
    _size = newsize;
  }

  void append(size_t n, char ch)
  {
    reserve(_size + n);
    for (size_t i = 0; i < n; ++i)
    {
      push_back(ch);
    }
  }

  Mystring &operator+=(const char *str)
  {
    append(str);
    return *this;
  }

  Mystring &insert(size_t pos, char ch)
  {
    assert(pos <= _size);
    if (_size == _capacity)
    {
      size_t newcapacity = _capacity == 0 ? 5 : _capacity * 2;
      reserve(newcapacity);
    }

    size_t end = _size + 1;
    while (end > pos)
    {
      _str[end] = _str[end - 1];
      end--;
    }
    _str[pos] = ch;
    ++_size;
    return *this;
  }

  Mystring &insert(size_t pos, const char *str)
  {
    assert(pos <= _size);
    size_t len = strlen(str);
    if (len == 0)
    {
      return *this;
    }
    if (len + _size > _capacity)
    {
      reserve(len + _size);
    }
    size_t end = _size + len;
    while (end >= pos + len)
    {
      _str[end] = _str[end - len];
      end--;
    }
    strncpy(_str + pos, str, len);
    _size += len;
    return *this;
  }

  void erase(size_t pos, size_t len = npos)
  {
    assert(pos < _size);
    if (len == npos || pos + len >= _size)
    {
      _str[pos] = '\0';
      _size = pos;
    }
    else
    {
      strcpy(_str + pos, _str + pos + len);
      _size -= len;
    }
  }

  size_t find(char ch, size_t pos = 0) const
  {
    assert(pos < _size);
    for (size_t i = pos; i < _size; ++i)
    {
      if (_str[i] == ch)
      {
        return i;
      }
    }
    return npos;
  }

  size_t Find_BF(const Mystring &substr, size_t pos = 0) const
  {
    // assert(str != nullptr);
    // assert(pos < _size);
    size_t n = substr.size();
    for (size_t i = pos; i < _size; ++i)
    {
      if (_str[i] == substr[0])
      {
        size_t j = 1;
        while(j < n && _str[i + j] == substr[j])
        {
          ++j;
        }
        if (j == n)
        {
          return i;
        }
      }
    }
    return npos;
  }

  size_t Find_KMP(const Mystring &substr, size_t pos = 0) const
  {
    // 预处理模式串，得到对应的next数组
    int m = _size;
    int n = substr.size();
    int next[n];
    substr.GetNext(next);

    // for (auto e : next)
    //   cout << e << " ";
    // cout << endl;

    // 利用next数组进行KMP模式匹配
    int i = pos, j = 0;
    while (i < m && j < n)
    {
      if (j == -1 || _str[i] == substr[j])
      {
        ++j;
        ++i;
      }
      else
      {
        j = next[j];
      }
    }

    if (j == n)
      return i - n;
    else
      return -1;
  }

  string substr(size_t pos, size_t len = npos) const
  {
    assert(pos < _size);
    if (len == npos || pos + len > _size)
    {
      len = _size - pos;
    }
    string sub;
    for (size_t i = 0; i < len; ++i)
    {
      sub += _str[pos + i];
    }
    return sub;
  }

  bool operator==(const Mystring &str) const
  {
    if (_size != str._size)
      return false;
    for (size_t i = 0; i < _size; ++i)
    {
      if (_str[i] != str._str[i])
      {
        return false;
      }
    }
    return true;
  }

  bool operator>(const Mystring &str) const
  {
    size_t i = 0;
    while (i < _size && i < str._size)
    {
      if (_str[i] != str._str[i])
      {
        return _str[i] > str._str[i];
      }
      ++i;
    }
    if (i < _size)
    {
      return true;
    }
    else
    {
      return false;
    }
  }

  bool operator!=(const Mystring &str) const
  {
    return !(*this == str);
  }

  bool operator>=(const Mystring &str) const
  {
    return (*this > str) || (*this == str);
  }

  bool operator<(const Mystring &str) const
  {
    return !(*this >= str);
  }

  bool operator<=(const Mystring &str) const
  {
    return !(*this > str);
  }

  const char *c_str() const
  {
    return _str;
  }

  size_t size() const
  {
    return _size;
  }

  void clear()
  {
    _str[0] = '\0';
    _size = 0;
  }

  char &operator[](size_t pos)
  {
    assert(pos < _size);
    return _str[pos];
  }

  const char &operator[](size_t pos) const
  {
    assert(pos < _size);
    return _str[pos];
  }

  typedef char *iterator;
  typedef const char *const_iterator;

  iterator begin()
  {
    return _str;
  }

  const_iterator begin() const
  {
    return _str;
  }

  iterator end()
  {
    return _str + _size;
  }

  const_iterator end() const
  {
    return _str + _size;
  }

  const static size_t npos = -1;

private:
  char *_str;
  size_t _size;
  size_t _capacity;

  void GetNext(int next[]) const
  {
    next[0] = -1;
    int k = -1; // 将k初始化为next[i-1]
    int i = 1;
    while (i < _size)
    {
      if (k == -1 || _str[i - 1] == _str[k])
      {
        next[i] = k + 1;
        ++k;
        ++i;
      }
      else
      {
        k = next[k];
      }
    }
  }
};

ostream &operator<<(ostream &out, const Mystring &str)
{
  for (size_t i = 0; i < str.size(); ++i)
  {
    out << str[i];
  }
  return out;
}

// istream& operator>>(istream& in, Mystring &str){
//   char ch;
//   ch = in.get();
//   while(ch != ' ' && ch != '\n')
//   {
//     str+=ch;
//     ch = in.get();
//   }
//   return in;
// }

istream &operator>>(istream &in, Mystring &str)
{
  str.clear();
  const size_t N = 32;
  char buff[N + 1];
  size_t i = 0;
  char ch;
  ch = in.get();
  while (ch != ' ' && ch != '\n')
  {
    buff[i++] = ch;
    if (i == N)
    {
      buff[i] = '\0';
      str += buff;
      i = 0;
    }
    ch = in.get();
  }
  buff[i] = '\0';
  str += buff;
  return in;
}
